By

文章目录
  1. 1. 介绍
  2. 2. 树的结构
  3. 3. 查找
  4. 4. 插入
  5. 5. 删除
  6. 6. 实际操练
  7. 7. 参考

介绍

二叉查找树（Binary Search Tree），又称二叉搜索树、二叉排序树。它符合这样的特征：

  • 它是一颗二叉树（空树也可以）
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树也也都是为二叉排序树。
      8    
    /   \
   3     10
 /   \     \
1     6     14
    /   \  /
   4    7 13

二叉查找树的搜索、插入、删除的时间复杂度等于O(h)，期望O(logn)，最坏O(n)

树的结构

它的结构和普通的二叉树一样

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 树的结构
 */
static class TreeNode{
	public int data=Integer.MIN_VALUE;//节点数据 
	public TreeNode left,right;//左右节点
	public TreeNode parent;//父节点  java里面加这个属性方便操作一点^_^
	
	public TreeNode(){};
	public TreeNode(int data){
		this.data=data;
	}
}

根据上面的定义，有tn.left.data<tn.data<tn.right.data

查找

二叉排序树种的查找过程为

  1. 若排序树tree是空树，则查找失败，直接返回，否则：
  2. 若x等于树的根节点的值，则查找成功，返回该节点；否则：
  3. 若x小于树的根节点的值，则搜索左子树；否则：
  4. 查找右子树。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /**
     * 查找操作
     * @param T  当前树的节点
     * @param x  查询点
     * @return
     */
    public static TreeNode search(TreeNode T,int x)
    {
    	if(T==null)//当前节点为null时表示没有找到
    		return null;
    	if(T.data==x)
    	{
    		return T;//表示查找成功
    	}else if(T.data>x)
    	{
    		//当前节点大于查询值的时候 进行左子节点的查找
    		return search(T.left,x);
    	}else{//否则进行右子节点的查找
    		return search(T.right,x);
    	}
    }

假如我现在查找的值为4的节点，则查找的路径为8->3->6->4 最终可以找到值

插入

二叉排序树的插入过程为：

  1. 若排序树为空树，这当前插入节点就是树的根节点，否则
  2. 判断x是否等于树当前节点的值，如果是，则不插入，否则
  3. 若x小于当前节点的值，如果此时当前节点的左子树为空，则直接插入到当前节点的左子树，否则将当前节点置为左子树进行第2步操作
  4. 若x大于当前节点的值，如果此时当前节点的右子树为空，则直接插入到当前节点的右子树，否则将当前节点置为右子树进行第2步操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 树的插入操作
 * @param T  树的根节点
 * @param x  需要插入的节点
 * @return  如果插入成功返回true,否则返回false
 */
public static boolean insert(TreeNode T,int x)
{
	if(T.data==Integer.MIN_VALUE)
	{
		T.data=x;//空节点的时候 插入点就是根节点
		return true;
	}
	
	TreeNode t=T;
	while(t!=null)
	{
		if(t.data==x)
		{
			return false;
		}else if(t.data>x)
		{
			if(t.left==null)
			{	//当前对比节点的左子节点为空了 直接插入就好了
				t.left=new TreeNode(x);
				t.left.parent=t;//更新父节点
			}else{
				t=t.left;//否则继续进行左子节点的查找
			}
		}else{
			if(t.right == null)
			{
				t.right=new TreeNode(x);
				t.right.parent=t;
			}else{
				t=t.right;
			}
		}
	}
	
	return true;
}

其实简单的版本就是先进行插入点得查找，如果找到点节点，则不插入，如果未找到，则直接插入到最后一个判断节点的后边即可。

假如我当前插入的值是5，则进行查找操作了，在找到4之后发现未找到该值的节点，并且5>4，所以5会插入到4的右孩子上

      8    
    /   \
   3     10
 /   \     \
1     6     14
    /   \  /
   4    7 13 
    \
     5

删除

二叉排序树的删除分为三种情况：

  • 当前删除的节点为叶子节点，也就是没有孩子节点，此时可以直接删除，将当前删除节点的父节点对应的孩子指向空即可

    比如要删除5，只需要将4的右子树指向空即可

  • 当前删除的节点仅含左子树或者右子树，这种情况下也是直接删除该节点即可，只不过是将当前删除的父节点对应的孩子指向删除节点对应的孩子即可

    比如要删除4，只需要将6的左子树指向5即可

  • 当前删除的节点的左右子树都存在，此时先查找删除节点的左子树的最大值，然后删除迭代删除该节点，最后将删除节点的值更新为最大值即可（注意这是一个递归过程..）

    比如要删除6，则先找它左子树的最大值为5，这个时候要删除5这个节点，然后将6的值域更新为5即可

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
 * 删除节点
 * @param T  树的跟
 * @param x  需要删除的值
 * @return
 */
public static boolean delete(TreeNode T,int x)
{
	TreeNode t=search(T,x);
	if(t!=null)
	{
		int isExistLeft=t.left!=null?1:0;
		int isExistRight=t.right!=null?1:0;
		
		switch(isExistLeft|isExistRight<<1)
		{
		case 0://the leaf node
			deleteMySelf(t);
			break;
		case 1://only left
			deleteOnlyLeft(t);
			break;
		case 2://obly right
			deleteOnlyRight(t);
			break;
		case 3://both child
			TreeNode maxT=findMaxNodeInLeft(t);//先查找当前节点中左子树中最大的节点
			delete(T,maxT.data);//删除那个节点
			t.data=maxT.data;//然后更新当前节点中的值  即可
			break;
		default:
			throw new AssertionError("no no no,somehing must be wrong!");
		
		}
		return true;
	}else{
		return false;//没有找到该节点
	}
}

/**
 * 删除我自己
 * @param t
 */
private static void deleteMySelf(TreeNode t){
	if(t.parent!=null)
	{
		if(t.parent.left==t)
		{
			t.parent.left=null;//直接删除我自己
		}else{
			t.parent.right=null;
		}
	}else{
		t.parent.right=new TreeNode();//相当于初始化根节点
	}
}

/**
 * 当前节点仅含左子树的情况下进行删除
 * @param t
 */
private static void deleteOnlyLeft(TreeNode t)
{
	if(t.parent!=null)
	{
		if(t.parent.left==t)
		{
			t.parent.left=t.left;//直接删除当前节点t
		}else{
			t.parent.right=t.left;
		}
		t.left.parent=t.parent;
	}else{
		//根节点被删除
		t.data=t.left.data;
		t.left=t.left.left;
		t.right=t.left.right;
	}
}

/**
 * 当前节点仅含左右树的情况下进行删除
 * @param t
 */
private static void deleteOnlyRight(TreeNode t)
{
	if(t.parent!=null)
	{
		if(t.parent.left==t)
		{
			t.parent.left=t.right;//直接删除当前节点t
		}else{
			t.parent.right=t.right;
		}
		t.right.parent=t.parent;
	}else{
		//根节点被删除
		t.data=t.right.data;
		t.left=t.left.left;
		t.right=t.left.right;
	}
}

/**
 * 查找左子树中最大的节点
 * @param T
 * @return
 */
private static TreeNode findMaxNodeInLeft(TreeNode T)
{
	TreeNode t=T.left;
	if(t!=null)
	while(t.right!=null)
	{
		t=t.right;//因为肯定右子树更加大
	}
	
	return t;
	
}

实际操练

最后关于上文中各个操作的操练代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
	TreeNode root=new TreeNode();
	root.parent=new TreeNode(Integer.MAX_VALUE);//凭空设置一个超级根节点  
	root.parent.right=root;//超级根节点接管根节点
	insert(root,8);
	insert(root,3);
	insert(root,10);
	insert(root,1);
	insert(root,6);
	insert(root,14);
	insert(root,4);
	insert(root,7);
	insert(root,13);//上面的insert是构建排序二叉树
	insert(root,5);//再次进行插入操作
	System.out.println(root);
	delete(root,3);//删除操作
	System.out.println(root);
}

参考

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 介绍
  2. 2. 树的结构
  3. 3. 查找
  4. 4. 插入
  5. 5. 删除
  6. 6. 实际操练
  7. 7. 参考